package com.cuz.daileetcode.暴力递归记忆化搜索动态规划;

import com.cuz.daileetcode.utils.ArrayUtils;

import java.util.Arrays;

/**
 * @author cuzz
 * @version 1.0
 * @description: 【题目】
 * 给定数组arr, arr中所有的值都为正数且不重复。每个值代表一种面值的货币，
 * 每种面值的货币可以使用1张，
 * 再给定一个整数aim，代表要找的钱数，求组成aim的最少货币数。
 * @date 14:21 2022/1/8
 **/
public class MinAmountMoneyToChange {


    public static void main(String[] args) {
        int[] money = {2, 3, 100, 2};
        //int count = Recursion.minAmountMoneyToChange(money, 5);
        //System.out.println(count);
        int count = DynamicProgramming.minAmountMoneyToChange(money, 7);
        System.out.println(count);
    }

    /****
     * 递归解法
     */
    static class Recursion {
        /***
         * 最少使用多少张 amountArray 中钱才能凑出目标钱
         * @param amountArray 货币数组
         * @param targetMoneyToChange 目标凑成钱
         * @return 最少使用几张
         */
        static int minAmountMoneyToChange(int[] amountArray, int targetMoneyToChange) {
            return recursion(amountArray, 0, targetMoneyToChange);
        }

        /***
         * 对当前钱的选择做出抉择
         * 可以选择不选择当前的钱，也可以选择当前的钱，取小者
         * 如果选择当前钱，无法凑出目标钱数 那么返回-1
         * @param amountArray 货币数组
         * @param nowChooseIndex 当前选择到amountArray的那个位置的硬币
         * @param restMoney 剩余的需要凑出来的钱
         * @return 当前决策最少需要多少张（可以选择不选择当前的钱，也可以选择当前的钱，取小者）
         */
        static int recursion(int[] amountArray, int nowChooseIndex, int restMoney) {
            //当前剩余的钱为0
            if (restMoney == 0) {
                //返回0 表示不选择当前位置的钱，所以选择对凑出目标钱数的影响是0
                return 0;
            }
            if (restMoney < 0) {
                //如果restMoney小于0 说明选择的钱太多了，之前做的选择是错误的
                return -1;
            }
            //如果当前选择的已经到达货币数组的极限 没有办法选择更多的钱了
            if (nowChooseIndex >= amountArray.length) {
                return -1;
            }
            //能走到这儿说明 剩余的钱不为0，也不为负数，且还有选择的机会
            //如果不选择当前的钱 选择的位置+1（向后做出选择）剩余的前数不变因为我们不选择当前的钱
            int noChooseNow = recursion(amountArray, nowChooseIndex + 1, restMoney);
            //选择当前的钱 剩余钱减少当前选择钱的面值
            int chooseNow = recursion(amountArray, nowChooseIndex + 1, restMoney - amountArray[nowChooseIndex]);
            //无论是否选择当前钱 or 不选择当前钱，都木有办法凑出目标钱 那么返回-1
            //如100，200，300，凑5，选择100 or不选择100都没法凑出5返回-1
            if (noChooseNow == -1 && chooseNow == -1) {
                return -1;
            }
            //如果不选择当前钱，我们再也无法凑出来目标面值的钱
            //比如2 100 3凑5 如果放弃了2我们再也没有办法凑出5元钱了 所以我们必须持有这张2
            if (noChooseNow == -1) {
                //那么我们必须做出选择当前钱的抉择，选择当前钱那么+1（因为选择了当前钱，张数+1）
                return chooseNow + 1;
            }
            //选择当前钱了我们再也无法凑出目标钱 那么我们只能做出不选择当前钱的抉择
            //比如 100，2，3凑出5 选择了100我们不可能凑出5了 我们只能放弃100
            if (chooseNow == -1) {
                return noChooseNow;
            }
            //反之我们可以选择选当前钱，可以 不选择当前钱，因为找最少的货币数
            //那么取较小者
            return Math.min(chooseNow + 1, noChooseNow);
        }
    }

    /***
     * 动态规划
     */
    static class DynamicProgramming {
        /***
         * 最少使用多少张 amountArray 中钱才能凑出目标钱
         * @param amountArray 货币数组
         * @param targetMoneyToChange 目标凑成钱
         * @return 最少使用几张
         */
        static int minAmountMoneyToChange(int[] amountArray, int targetMoneyToChange) {
            int len = amountArray.length;
            int[][] dp = new int[len + 1][targetMoneyToChange + 1];
            //初始化
            Arrays.fill(dp[0], 0);
            for (int col = 1; col < targetMoneyToChange + 1; col++) {
                dp[len][col] = -1;
            }
            System.out.println(ArrayUtils.toString(dp));
            for (int nowChooseIndex = len - 1; nowChooseIndex >= 0; nowChooseIndex--) {
                for (int restMoney = 1; restMoney <= targetMoneyToChange; restMoney++) {
//                    int noChooseNow = valueInAmountArray(dp, nowChooseIndex + 1, restMoney);
//                    int chooseNow = valueInAmountArray(dp, nowChooseIndex + 1, restMoney - amountArray[nowChooseIndex]);
//                    dp[nowChooseIndex][restMoney] = doPolicyDecision(noChooseNow, chooseNow);
                    int noChooseNow = dp[nowChooseIndex + 1][restMoney];
                    int chooseNow = -1;
                    if (restMoney - amountArray[nowChooseIndex] >= 0) {
                        chooseNow = dp[nowChooseIndex + 1][restMoney - amountArray[nowChooseIndex]];
                    }
                    if (noChooseNow == -1 && chooseNow == -1) {
                        dp[nowChooseIndex][restMoney] = -1;
                        continue;
                    }
                    //如果不选择当前钱，我们再也无法凑出来目标面值的钱
                    //比如2 100 3凑5 如果放弃了2我们再也没有办法凑出5元钱了 所以我们必须持有这张2
                    if (noChooseNow == -1) {
                        //那么我们必须做出选择当前钱的抉择，选择当前钱那么+1（因为选择了当前钱，张数+1）
                        dp[nowChooseIndex][restMoney] = chooseNow + 1;
                        continue;
                    }
                    //选择当前钱了我们再也无法凑出目标钱 那么我们只能做出不选择当前钱的抉择
                    //比如 100，2，3凑出5 选择了100我们不可能凑出5了 我们只能放弃100
                    if (chooseNow == -1) {
                        dp[nowChooseIndex][restMoney] = noChooseNow;
                        continue;
                    }
                    //反之我们可以选择选当前钱，可以 不选择当前钱，因为找最少的货币数
                    //那么取较小者
                    dp[nowChooseIndex][restMoney] = Math.min(chooseNow + 1, noChooseNow);
                }
            }
            System.out.println(ArrayUtils.toString(dp));
            return dp[0][targetMoneyToChange];
        }

        static int minAmountMoneyToChange2(int[] amountArray, int targetMoneyToChange) {
            int len = amountArray.length;
            int[][] dp = new int[len + 1][targetMoneyToChange + 1];
            Arrays.fill(dp[0], 0);
            for (int col = 1; col <= targetMoneyToChange; col++) {
                dp[len][col] = -1;
            }
            for (int index = len - 1; index >= 0; index--) {
                for (int rest = 1; rest <= targetMoneyToChange; rest++) {
                    int p1 = dp[index + 1][rest];
                    int p2Next = -1;
                    if (rest - amountArray[index] >= 0) {
                        p2Next = dp[index + 1][rest - amountArray[index]];
                    }
                    if (p1 == -1 && p2Next == -1) {
                        dp[index][rest] = -1;
                        continue;
                    }
                    //如果不选择当前钱，我们再也无法凑出来目标面值的钱
                    //比如2 100 3凑5 如果放弃了2我们再也没有办法凑出5元钱了 所以我们必须持有这张2
                    if (p1 == -1) {
                        //那么我们必须做出选择当前钱的抉择，选择当前钱那么+1（因为选择了当前钱，张数+1）
                        dp[index][rest] = p2Next + 1;
                        continue;
                    }
                    //选择当前钱了我们再也无法凑出目标钱 那么我们只能做出不选择当前钱的抉择
                    //比如 100，2，3凑出5 选择了100我们不可能凑出5了 我们只能放弃100
                    if (p2Next == -1) {
                        dp[index][rest] = p1;
                        continue;
                    }
                    //反之我们可以选择选当前钱，可以 不选择当前钱，因为找最少的货币数
                    //那么取较小者
                    dp[index][rest] = Math.min(p1, p2Next + 1);
                }
            }
            return dp[0][targetMoneyToChange];
        }
    }
}
